package main.Q401_500;

import java.util.*;

public class Q401_410 {
    public static void main(String[] args) {
        System.out.println("Question401：二进制手表");
        System.out.println("Question402：移除K位数字");
        System.out.println("Question403：");
        System.out.println("Question404：左叶子之和");
        System.out.println("Question405：数字转换未十六进制数");
        System.out.println("Question406：根据身高重建队列");
        System.out.println("Question407：");
        System.out.println("Question408：");
        System.out.println("Question409：最长回文串");
        System.out.println("Question410：");
    }
}

class Question401{//未完成
    public List<String> readBinaryWatch(int turnedOn) {
        int[] hours={1,2,4,8};
        int[] minutes={1,2,4,8,16,32};
        List<String> list=new ArrayList<>();
        for (int i=0;i<=turnedOn;i++){

        }
        return null;
    }
}

class Question402{
    public String removeKdigits(String num, int k) {
        Deque<Character> deque=new LinkedList<>();
        char[] str=num.toCharArray();
        int i=0;
        while (i< str.length&&k>0){
            if (deque.isEmpty()||str[i]>deque.peekLast()) deque.addLast(str[i]);//队空或入队大于队尾
            else {
                while (!deque.isEmpty()&&k>0&&deque.peekLast()>str[i]){//当队不空、k>0、队尾元素大于等于入队元素时
                    deque.pollLast();
                    k--;
                }
                deque.addLast(str[i]);
            }
            i++;
        }
        while (i<str.length) deque.addLast(str[i++]);//将未入队字符入队
        while (k>0&&!deque.isEmpty()) {
            deque.pollLast();
            k--;
        }
        StringBuffer result=new StringBuffer();
        if (deque.isEmpty()) result.append("0");
        else {
            while (!deque.isEmpty()&&deque.peekFirst()=='0') deque.pollFirst();//删除前导0
            if (deque.isEmpty()) result.append("0");
            else {
                while (!deque.isEmpty()) result.append(deque.pollFirst());
            }
        }
        return result.toString();
    }
}

class Question404{
    public int sumOfLeftLeaves(TreeNode root) {
        int sum=0;
        if (root!=null){
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()){
                TreeNode curNode=queue.poll();
                if (curNode.left!=null){
                    TreeNode curLeft=curNode.left;
                    if (curLeft.left==null&&curLeft.right==null) sum+= curLeft.val;
                    queue.add(curNode.left);
                }
                if (curNode.right!=null) queue.add(curNode.right);
            }
        }
        return sum;
    }
}

class Question405{
    public String toHex(int num) {
        return Integer.toHexString(num);
    }
}

class Question406{
    public int[][] reconstructQueue(int[][] people) {
        int length= people.length;
        int[][] sort=new int[length][];
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0]==o2[0]){
                    return o2[1]-o1[1];//等身高时，降序排列人数
                }else return o1[0]-o2[0];//身高升序排列
            }
        });
        for (int[] person:people){//person前有多少人，则person放置在空位置中第person[1]+1的位置
            int index=person[1]+1;
            for (int i=0;i<length;i++){
                if (sort[i]==null) index--;//空位置才能被纳入考虑范围
                if (index==0) {
                    sort[i]=person;
                    break;
                }
            }
        }
        return sort;
    }
}

class Question409{
    public int longestPalindrome(String s) {//最长回文串为，所有偶数个字符个数相加再加上最大的奇数字符个数
        int[] charCount=new int[123];
        int length=0;
        for (char c:s.toCharArray()) charCount[c]++;
        Arrays.sort(charCount);
        for (int v:charCount){
            length+=v/2*2;
            if (v%2==1&&length%2==0) length++;
        }
        return length;
    }
}